package at.billix.gwt.client;

import com.google.gwt.core.client.*;
import com.google.gwt.json.client.*;
import java.util.*;

public class Prolog {

	protected static final int GRAMMAR	= 1;
	protected static final int GOAL		= 2;
	
	protected String sGrammar;
	protected JavaScriptObject grammar;
	
	public Prolog(String g) {
		sGrammar = g;
	}
	
	protected native JavaScriptObject eval(int action, String sGrammar, JavaScriptObject grammar, String goal) /*-{
//
// renders an object to a string
//

function renderObject(obj, quotes) {
	if (!obj || obj == null) return "undefined or null";
	var sb = new StringBuffer().append(obj instanceof Array ? "[ " : "{ ");
	var a = [];
	var atts = [];
	for (var i in obj) atts.push(i);
	atts.sort();
	for (var j in atts) {
		var i = atts[j];
		var v = obj[i];
		if (typeof(v) != "function") {
			a.push(new StringBuffer().append(quotes ? "\"" + i + "\"" : i).append(": ")
				.append(typeof(v) == "object" ? renderObject(v, quotes) : (quotes && typeof(v) == "string" ? "\"" + serialize(v) + "\"" : v)).toString());
		}
	}
	return sb.append(a.join(", ")).append(obj instanceof Array ? " ]" : " }").toString();
}

//
// clones an object
//

function cloneObject(obj) {
	var obj2 = {};
	for (var i in obj) obj2[i] = obj[i];
	return obj2;
}

//
// unifies two objects
//

function unify(obj1, obj2) {
	var r = {};
	for (var i in obj1) {
		var v2 = obj2[i];
		if (v2) {
			var v1 = obj1[i];
			if (typeof(v1) == "string" && typeof(v2) == "string"  && v1 == v2) r[i] = v1;
			else if (typeof(v1) == "number" && typeof(v2) == "number"  && v1 == v2) r[i] = v1;
			else if (typeof(v1) == "object" && typeof(v2) == "object") {
				var v = unify(v1, v2);
				if (!v) return false;
				r[i] = v;
			} else {
				return false;
			}
		} else r[i] = obj1[i];
	}
	for (var i in obj2) {
		if (!r[i]) r[i] = obj2[i];
	}
	return r;
}

//
// unifies two objects, considers variables too
//

function unifyWithVars(obj1, obj2, vars, _varId) {
	var varId = _varId || {};
	var r = {};
	for (var i in obj1) {
		var v2 = obj2[i];
		if (v2) {
			var v1 = obj1[i];
			if (typeof(v2) == "string" && v2.length > 0 && v2.charAt(0) == "$"
			  && typeof(v1) == "string" && v1.length > 0 && v1.charAt(0) == "$") {
			  	v1 = getPrimaryVar(v1, varId);
			  	v2 = getPrimaryVar(v2, varId);
				var v3 = vars[v1];
				var v4 = vars[v2];
				if (v3 && v4) {
					var v = unifyWithVars({ tmp: v3 }, { tmp: v4 }, vars, varId);
					if (!v) return false; else r[i] = v.tmp;
				} else if (v3) {
					r[i] = vars[v2] = v3;
				} else if (v4) {
					r[i] = vars[v1] = v4;
				} else {
					r[i] = varId[v1] = v2;
				}
			} else if (typeof(v2) == "string" && v2.length > 0 && v2.charAt(0) == "$") {
				v2 = getPrimaryVar(v2, varId);
				var v3 = vars[v2];
				if (!v3) {
					vars[v2] = v1;
					r[i] = v1;
				} else {
					var v = unifyWithVars({ tmp: v3 }, { tmp: v1 }, vars, varId);
					if (!v) return false;
					vars[v2] = v.tmp;
					r[i] = v.tmp;
				}
			} else if (typeof(v1) == "string" && v1.length > 0 && v1.charAt(0) == "$") {
				v1 = getPrimaryVar(v1, varId);
				var v3 = vars[v1];
				if (!v3) {
					vars[v1] = v2;
					r[i] = v2;
				} else {
					var v = unifyWithVars({ tmp: v3 }, { tmp: v2 }, vars, varId);
					if (!v) return false;
					vars[v1] = v.tmp;
					r[i] = v.tmp;
				}
			} else if (typeof(v1) == "string" && typeof(v2) == "string"  && v1 == v2) r[i] = v1;
			else if (typeof(v1) == "number" && typeof(v2) == "number"  && v1 == v2) r[i] = v1;
			else if (typeof(v1) == "object" && typeof(v2) == "object") {
				var v = unifyWithVars(v1, v2, vars, varId);
				if (!v) return false;
				r[i] = v;
			} else {
				return false;
			}
		}
	}
	for (var i in obj2) {
		if (!r[i]) {
			var v = obj2[i];
			r[i] = replaceVars(v, vars, varId);
		}
	}
	for (var i in obj1) {
		if (!r[i]) {
			var v = obj1[i];
			r[i] = replaceVars(v, vars, varId);
		}
	}
	return r;
}

// gets the primary variable according to the variable identity

function getPrimaryVar(var1, varId) {
	var var2 = varId[var1];
	if (var2 && typeof(var2) == "string" && var2.length > 0 && var2.charAt(0) == "$") {
		return getPrimaryVar(var2, varId);
	}
	return var1;
}

// replaces all bound variables in an object

function replaceVars(obj, vars, varId) {
	if (typeof(obj) == "string" && obj.length > 0 && obj.charAt(0) == "$") {
		var v = vars[getPrimaryVar(obj, varId)];
		if (v) return v; else return obj;
	} else if (typeof(obj) == "object") {
		var obj2 = {};
		for (var i in obj) {
			obj2[i] = replaceVars(obj[i], vars, varId);
		}
		return obj2;
	} else return obj;
}

//
// a string buffer
//

function StringBuffer() {
   this.buffer = [];
}

// appends a string to the buffer

StringBuffer.prototype.append = function(text) {
	this.buffer.push(text);
	return this;
}

// gets the joined string

StringBuffer.prototype.toString = function() {
	return this.buffer.join("") 
}

//
// a simple text tokenizer that splits a string in tokens like identifiers,
// quoted strings, numbers and operators
//

function Tokenizer(text) {
	this.text = text;
	this.token = null;
	this.pos = 0;
	this.line = 1;
}

// true if there are still tokens to be read

Tokenizer.prototype.hasNext = function() {
	if (this.pos < this.text.length) {
		var c = this.text.charAt(this.pos);
		while (this.isWhiteSpace(c)) {
			this.pos++;
			if (this.pos >= this.text.length) return false;
			c = this.text.charAt(this.pos);
		}
		return true;
	} else return this.pos < this.text.length;
}

// gets the next token

Tokenizer.prototype.nextToken = function() {
	var c = this.text.charAt(this.pos);
	var test = null;
	if (this.isAlphabetic(c)) test = Tokenizer.prototype.isAlphanumeric;
	else if (this.isNumeric(c)) test = Tokenizer.prototype.isNumeric;
	else {
		this.pos++;
		return this.token = c;
	}
	var sb = new StringBuffer().append(c);
	this.pos++;
	while (this.pos < this.text.length) {
		c = this.text.charAt(this.pos);
		if (test(c)) {
			sb.append(c);
			this.pos++;
		} else break;
	}
	return this.token = sb.toString();
}

// true if the string is alphabetic

Tokenizer.prototype.isAlphabetic = function(s) {
	for (var i = 0; i < s.length; i++) {
		var c = s.charAt(i);
		if (!(c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z' || c > '~')) return false;
	}
	return true;
}

// true if the character is numeric

Tokenizer.prototype.isNumeric = function(c) {
	return c >= '0' && c <= '9';
}

Tokenizer.prototype.isAlphanumeric = function(c) {
	return Tokenizer.prototype.isAlphabetic(c) || Tokenizer.prototype.isNumeric(c);
}

// true if the character is a white space

Tokenizer.prototype.isWhiteSpace = function(c) {
	if (c == "\n") this.line++;
	return c == " " || c == "\n";
}

Tokenizer.prototype.alert = function(msg) {
	alert("Error on line " + this.line + ": " + msg);
}

		function parsePredicate(tokenizer) {
			if (!tokenizer.hasNext()) { tokenizer.alert("Unexpected end of string"); return null; }
			tokenizer.nextToken();
			if (!tokenizer.isAlphabetic(tokenizer.token.charAt(0))) { tokenizer.alert("Identifier expected"); return null; }
			var name = tokenizer.token;
			if (!tokenizer.hasNext()) return { name: name };
			tokenizer.nextToken();
			if (tokenizer.token != "(") return { name: name };
			var args = [];
			while (true) {
				var arg = parsePredicate(tokenizer);
				if (arg == null) return null;
				args.push(arg);
				if (tokenizer.token == ")") return { name: name, args: args };
				if (tokenizer.token != ",") { tokenizer.alert("',' expected"); return null; }
			}
		}

		function parseRule(tokenizer) {
			var head = parsePredicate(tokenizer);
			if (head == null) return null;
			if (!tokenizer.hasNext()) { tokenizer.alert("Unexpected end of string"); return null; }
			tokenizer.nextToken();
			if (tokenizer.token == ".") return { head: head };
			if (tokenizer.token != ":") { tokenizer.alert("':-' expected"); return null; }
			if (!tokenizer.hasNext()) { tokenizer.alert("Unexpected end of string"); return null; }
			tokenizer.nextToken();
			if (tokenizer.token != "-") { tokenizer.alert("':-' expected"); return null; }
			var tail = [];
			while (true) {
				var pred = parsePredicate(tokenizer);
				if (pred == null) return null;
				tail.push(pred);
				if (!tokenizer.hasNext()) { tokenizer.alert("Unexpected end of string"); return null; }
				tokenizer.nextToken();
				if (tokenizer.token == ".") return { head: head, tail: tail };
				if (tokenizer.token != ",") { tokenizer.alert("',' expected"); return null; }
			}
		}
		
		function parseGrammar(tokenizer) {
			var rules = [];
			while (tokenizer.hasNext()) {
				var rule = parseRule(tokenizer);
				if (rule == null) return null;
				rules.push(rule);
			}
			return rules;
		}
		
//
// an atomic fact
//

function Fact(name, args) {
	this.name = name;
	this.args = args;
}

Fact.prototype.toString = function() {
	return this.name + "/" + renderArray(this.args);
}

Fact.prototype.unify = function(fact, _vars, _varId) {
	if (this.name != fact.name || this.args.length != fact.args.length) return false;
	var vars = _vars || {};
	var varId = _varId || {};
	var args = [];
	for (var i = 0; i < this.args.length; i++) {
		var a1 = this.args[i];
		var a2 = fact.args[i];
		var a3 = unifyWithVars(a1, a2, vars, varId);
		if (!a3) return false; else args.push(a3);
	}
	return { args: args, vars: vars, varId: varId };
}

//
// built-in ("common") "facts"
//

function FactEqual() {
}

FactEqual.prototype = new Fact("=", [ {}, {} ]);

FactEqual.prototype.unify = function(fact, _vars, _varId) {
	if (this.name != fact.name || this.args.length != fact.args.length) return false;
	var vars = _vars || {};
	var varId = _varId || {};
	var s = renderObject(vars);
	var r = unifyWithVars(fact.args[0], fact.args[1], vars, varId);
	return r ? { args: null, vars: vars, varId: varId } : false;
}

function FactNotEqual() {
}

FactNotEqual.prototype = new Fact("!=", [{}, {}]);

FactNotEqual.prototype.unify = function(fact, _vars, _varId) {
	if (this.name != fact.name || this.args.length != fact.args.length) return false;
	var vars = _vars || {};
	var varId = _varId || {};
	var s = renderObject(vars);
	var r = unifyWithVars(fact.args[0], fact.args[1], vars, varId);
	return !r ? { args: null, vars: vars, varId: varId } : false;
}

//
// a complex rule
//

function Rule(head, tail) {
	this.head = head;
	this.tail = tail;
}

Rule.prototype.apply = function(goal, _vars, _varId) {
	var vars = _vars || {};
	var varId = _varId || {};
	this.raiseVars(vars, varId);
	goal = this.raiseFact(goal);
	var r = goal.unify(this.head, vars, varId);
	if (!r) return false;
	var rs = [];
	var r = this.tryList(this.tail, 0, vars, varId, rs);
	if (!r) return false;
	var rule = this;
	rs = mapList(rs, function(v) { rule.lowerVars(v, varId); return v; });
	return rs;
}

Rule.prototype.tryList = function(list, pos, vars2, varId2, result) {
	var rs = this.kb.ask(list[pos], vars2, varId2);
	if (!rs) return false;
	if (pos + 1 == list.length) {
		addAll(rs, result);
		return true;
	} else {
		var found = false;
		for (var i in rs) {
			var vars3 = cloneObject(vars2);
			var varId3 = cloneObject(varId2);
			addAll(rs[i], vars3);
			var r = this.tryList(list, pos + 1, vars3, varId3, result);
			if (r) found = true;
		}
		return found;
	}
}

Rule.prototype.lowerVars = function(vars, varId) {
	var keys = [];
	for (var i in vars) {
		if (i.indexOf("$") == 0 && i.indexOf("$_") == -1) {
			var v2 = vars[i];
			if (v2) {
				for (var k in varId) {
					var v = varId[k];
					if (!vars[k] && v == i) {
						vars[k] = v2;
						delete vars[i];
					}
				}
			}
		}
	}
	var keys = [];
	for (var i in vars) {
		keys.push(i);
	}
	for (var i in keys) {
		var key = keys[i];
		if (key.indexOf("$_") == 0) {
			var v = vars[key];
			vars[key.substring(2)] = typeof(v) == "string" && v.length > 0 && v.charAt(0) == "$" ?  v.substring(2) : v;
		}
		delete vars[key];
	}
}

Rule.prototype.raiseFact = function(fact) {
	var rule = this;
	var args = mapList(fact.args, function(obj) { return rule.raiseObject(obj); });
	return new Fact(fact.name, args);
}

Rule.prototype.raiseObject = function(obj) {
	if (typeof(obj) == "string" && obj.length > 0 && obj.charAt(0) == "$") {
		return "$_" + obj;
	} else if (typeof(obj) == "object") {
		var obj2 = {};
		for (var i in obj) {
			obj2[i] = this.raiseObject(obj[i]);
		}
		return obj2;
	} else return obj;
}

Rule.prototype.raiseVars = function(vars, varId) {
	var keys = [];
	for (var i in vars) {
		keys.push(i);
	}
	for (var i in keys) {
		var key = keys[i];
		var v = vars[key];
		delete vars[key];
		vars["$_" + key] = typeof(v) == "string" && v.length > 0 && v.charAt(0) == "$" ?  "$_" + v : v;
	}
	
	keys = [];
	for (var i in varId) {
		keys.push(i);
	}
	for (var i in keys) {
		var key = keys[i];
		var v = varId[key];
		delete varId[key];
		varId["$_" + key] = "$_" + v;
	}
}

//
// a knowledge base
//

function KnowledgeBase() {
	this.facts = [];
	this.rules = [];
}

KnowledgeBase.prototype.add = function(obj) {
	if (obj instanceof Fact) {
		this.facts.push(obj);
	} else if (obj instanceof Rule) {
		this.rules.push(obj);
		obj.kb = this;
	} else alert("Unknown object to add");
}

KnowledgeBase.prototype.ask = function(goal, _vars, _varId) {
	var vars = _vars || {};
	var varId = _varId || {};
	var rs = [];
	var found = false;
	for (var i in this.facts) {
		var vars2 = cloneObject(vars);
		var varId2 = cloneObject(varId);
		var r = this.facts[i].unify(goal, vars2, varId2);
		if (r) { rs.push(r.vars); found = true; }
	}
	for (var i in this.rules) {
		var vars2 = cloneObject(vars);
		var varId2 = cloneObject(varId);
		var r = this.rules[i].apply(goal, vars2, varId2);
		if (r) { addAll(r, rs); found = true; }
	}
	return found ? rs : false;
}

KnowledgeBase.prototype.eval = function(goal, callback) {
	var rs = this.ask(goal);
	if (rs) {
		for (var i in rs) {
			var f = function(x) {
				setTimeout(function() { 
					callback(x);
				}, 0);
			};
			f(rs[i]);
		}
	}
	return rs != false;
}

//
// applies a function to all elements of an array
//

function mapList(a, f) {
	var a2 = [];
	for (var i in a) {
		a2.push(f(a[i]));
	}
	return a2;
}

//
// adds all elements to an object or an array
//

function addAll(obj1, obj2) {
	if (obj2 instanceof Array) {
		for (var i in obj1) obj2.push(obj1[i]);
	} else {
		for (var i in obj1) obj2[i] = obj1[i];
	}
}

function transformPredicate(pred) {
	if (!pred.args || pred.length == 0) {
		var name = pred.name;
		return new Fact(name.charAt(0).toUpperCase() == name.charAt(0) ? "$" + name : name, []);
	} else {
		var args = [];
		for (var i = 0; i < pred.args.length; i++) {
			var arg = pred.args[i];
			var name = arg.name;
			args.push({ param: name.charAt(0).toUpperCase() == name.charAt(0) ? "$" + name : name });
		}
		return new Fact(pred.name, args);
	}
}

function transformGrammar(rules) {
	var kb = new KnowledgeBase();
	kb.add(new FactEqual());
	kb.add(new FactNotEqual());
	for (var i = 0; i < rules.length; i++) {
		var rule = rules[i];
		var head = transformPredicate(rule.head);
		if (!rule.tail) {
			kb.add(head);
		} else {
			var tail = [];
			for (var j = 0; j < rule.tail.length; j++) {
				var pred = rule.tail[j];
				tail.push(transformPredicate(pred));
			}
			kb.add(new Rule(head, tail));
		}
	}
	return kb;
}

		// function body

		switch (action) {
			case 1:
				var tokenizer = new Tokenizer(sGrammar);
				var rules = parseGrammar(tokenizer);
				return transformGrammar(rules);
			case 2:
				var tokenizer = new Tokenizer(goal);
				goal = parsePredicate(tokenizer);
				var compiledGoal = transformPredicate(goal);
				var result = grammar.ask(compiledGoal);
				return { result: result };
		};
	}-*/;
	
	public Collection eval(String goal) {
		if (grammar == null) grammar = eval(GRAMMAR, sGrammar, null, null);
		JSONObject result = new JSONObject(eval(GOAL, null, grammar, goal));
		if (result.get("result") instanceof JSONBoolean) return null;
		else {
			JSONArray a = (JSONArray) result.get("result");
			Collection coll = new ArrayList();
			for (int i = 0; i < a.size(); i++) {
				JSONObject obj = (JSONObject) a.get(i);
				Map map = new HashMap();
				Iterator iter = obj.keySet().iterator();
				while (iter.hasNext()) {
					String key = iter.next().toString();
					map.put(key.substring(1), obj.get(key).toString());
				}
				coll.add(map);
			}
			return coll;
		}
	}

}

